Computer generated images are typically made up of many differing components or graphical elements which are rendered and composited together to create a final image. In recent times, an "opacity channel" (also known as a "matte", an "alpha channel", or simply "opacity") has been commonly used. The opacity channel contains information regarding the transparent nature of each element. The opacity channel is stored alongside each instance of a colour, so that, for example, a pixel-based image with opacity stores an opacity value as part of the representation of each pixel. An element without explicit opacity channel information is typically understood to be fully opaque within some defined bounds of the element, and assumed to be completely transparent outside those bounds.
An expression tree offers a systematic means or representation for rendering objects or elements of an image. Expression trees comprise a plurality of nodes including leaf nodes, internal nodes and a root node. A leaf node, being the outer most node of an expression tree, has no descendent nodes and consists of one or more graphical elements. An internal node typically branches to left and right subtrees, wherein each subtree is itself an expression tree comprising at least one leaf node. The internal nodes of an expression tree are compositing operators, which treat the left and right subtrees as operands of the operator. The first node of the expression tree is commonly referred to as a root node. The root node of an expression tree represents the final image, and each node of the tree represents a portion of the final image.
Although a graphical element may of itself be of a certain size, it need not be entirely visible in a final image, or only a portion of the element may have an effect on the final image. For example, assume an image of a certain size is to be displayed on a display. Howevever, if the image is positioned so that only the top left corner of the image is displayed by the display device, the remainder of the image is not displayed. The final image as displayed on the display device thus comprises the visible portion of the image, and the invisible portion in such a case need not be rendered.
Another way in which only a portion of an element may have an effect is when the portion is obscured by another element. For example, a final image to be displayed (or rendered) may comprise one or more opaque graphical elements, some of which obscure other graphical elements. Hence, the obscured elements have no effect on the final image.
If an element, or parts of elements, that have no effect on true final image can be identified, those elements (or parts) need not be rendered, thereby saving considerable time and possibly memory.
Problems arise with prior art methods, at least for images where overlaps occur, because these methods do not easily cope with transparent graphical objects, nor do they handle the full range of compositing operators. It is therefore desirable to at least ameliorate one or more of those problems.